10. CODE: Complete A* Search

Complete A* Search

In this exercise, you will complete AStarSearch() in route_planner.cpp using the NextNode, ConstructFinalPath, and AddNeighbors methods you have written previously.

## To complete this exercise:

  1. Delete the current contents of AStarSearch.
  2. Use the NextNode, ConstructFinalPath and AddNeighbors methods to implement the pseudocode below in AStarSearch:

## Pseudocode

AStarSearch:

  1. Set start_node->visited to be true.

  2. Push start_node to the back of open_list.

  3. Create a pointer RouteModel::Node *current_node and initialize the pointer to nullptr.

  4. while the open_list size is greater than 0:

    1. Set the current_node pointer to the results of calling NextNode.
    2. if the distance from current_node to the end_node is 0:
    • Call ConstructFinalPath using current_node and set m_Model.path with the results.
    • Return to exit the A* search.
    1. else call AddNeighbors with the current_node.

Workspace

This section contains either a workspace (it can be a Jupyter Notebook workspace or an online code editor work space, etc.) and it cannot be automatically downloaded to be generated here. Please access the classroom with your account and manually download the workspace to your local machine. Note that for some courses, Udacity upload the workspace files onto https://github.com/udacity, so you may be able to download them there.

Workspace Information:

  • Default file path:
  • Workspace type: react
  • Opened files (when workspace is loaded): n/a
  • userCode:

    export CXX=g++-7
    export CXXFLAGS=-std=c++17
    cmake_tests() {
    /usr/local/bin/cmake -DTESTING="AStarSearch" "$1"
    }
    export -f cmake_tests

Solution

Final A Star

Next Concept